package vn.com.epi.algorithm.knn;

import java.io.IOException;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

import org.apache.hadoop.hbase.client.HTable;
import org.apache.hadoop.hbase.client.Put;
import org.apache.hadoop.hbase.util.Bytes;

import com.google.common.collect.Lists;

import vn.com.epi.algorithm.clustering.Data;
import vn.com.epi.algorithm.clustering.KMeans;
import vn.com.epi.algorithm.clustering.Point;
import vn.com.epi.algorithm.kdtree.KDTree;
import vn.com.epi.data.table.NeighbourTable;
import vn.com.epi.utils.StringUtils;

public class KNN {

	private static final int K_NEAREST = 5;
	private static final String METHOD = "brute-force";	
	
	private static class BruteForce {
		
		private int n;
		private int[] label;
		
		public BruteForce() {

		}
		
		public void setLabel(int[] lb) {
			n = lb.length;
			label = new int[n];
			for (int i = 0; i < n; i++)
				label[i] = lb[i];			
		}

		public int[] nearest(int index, int k) {		
			int[] r = new int[k];
			double[] val = new double[k];
			for (int i = 0; i < k; i++)
				val[i] = 0;
			for (int i = 0; i < n; i++)
				if (label[i] != index) {
					double sim = Data.distance(label[i], index);
					for (int j = 0; j < k; j++)
						if (val[j] < sim) {
							for (int t = k - 1; t > j; t--) {
								val[t] = val[t - 1];
								r[t] = r[t - 1];
							}
							val[j] = sim;
							r[j] = label[i];
							break;
						}
				}
			return r;
		}
	}
	
	private int dimensional;	
	private BruteForce force;
	private Map<Integer, String> nearest;
	
	public KNN() {
		nearest = new HashMap<Integer, String>();
		force = new BruteForce();
	}
	
	public KNN(int d) {
		nearest = new HashMap<Integer, String>();
		force = new BruteForce();
		dimensional = d;
	}
	
	public Map<Integer, String> getNearest() {
		return nearest;
	}

	private int getNumClusters(int n) {
		if (n >= 500000)
			return 200;
		else
			if (n >= 300000)
				return 150;
			else
				if (n >= 100000)
					return 100;
				else
					if (n >= 70000)
						return 50;
					else
						if (n >= 40000)
							return 20;
						else
							if (n >= 20000)
								return 15;
							else
								if (n >= 10000)
									return 9;
								else
									if (n >= 7000)
										return 5;
									else
										if (n >= 6000)
											return 4;
										else
											if (n >= 4000)
												return 3;
											else
												if (n >= 2000)
													return 2;
		return 1;
	}
	
	private int getNumIterators(int n) {
		if (n >= 500000)
			return 5;
		else
			if (n >= 300000)
				return 7;
			else
				if (n >= 100000)
					return 10;
				else
					if (n >= 70000)
						return 15;
					else
						if (n >= 40000)
							return 20;
						else
							if (n >= 20000)
								return 25;
							else
								if (n >= 10000)
									return 30;
								else
									if (n >= 7000)
										return 35;
									else
										if (n >= 2000)
											return 40;
		return 50;
	}
	
	private int[] vector(int index) {
		int[] v;
		v = new int[dimensional];
		for (int i = 0; i < dimensional; i++)
			v[i] = 0;
		for (Point p: Data.users[index]) {
			v[p.getIndex()] = p.getValue();
		}
		return v;
	}
	
	public void optimize(int n, int[] label) {
		if (n < 2000) {
			if (METHOD.compareTo("kdtree") == 0) {
				KDTree tree = new KDTree(dimensional);
				for (int i = 0; i < n; i++) {
					int j = label[i];
					int[] key = vector(j);
					tree.insert(key, i);
				}
				for (int i = 0; i < n; i++) {
					int index = label[i];
					int[] key = vector(index);
					Object[] obj = tree.nearest(key, K_NEAREST + 1);
					StringBuilder sb = new StringBuilder();
					for (int j = 0; j < obj.length; j++) {
						int near = label[(Integer) obj[j]];
						 sb.append(near).append(",");
					}
					if (sb.length() > 0) {
						sb.deleteCharAt(sb.length() - 1);
						nearest.put(index, sb.toString());
					}
				}
			} else {
				force.setLabel(label);			
				for (int i = 0; i < n; i++) {
					int index = label[i];
					int[] obj = force.nearest(index, K_NEAREST);
					StringBuilder sb = new StringBuilder();
					for (int j = 0; j < obj.length; j++) {
						int near = obj[j];
						sb.append(near).append(",");
					}
					if (sb.length() > 0) {
						sb.deleteCharAt(sb.length() - 1);
						nearest.put(index, sb.toString());
					}
				}
			}
		} else {
			int k, iterators;
			k = getNumClusters(n);
			iterators = getNumIterators(n);
			KMeans kmean = new KMeans(n, k, iterators, label);
			kmean.approximateAlgorithm();
			@SuppressWarnings("static-access")
			int kCluster = kmean.kClusters;
			for (int i = 0; i < kCluster; i++) {
				int size = kmean.cluster[i].size();
				int[] lb = new int[size];
				int j = 0;
				for (int z: kmean.cluster[i]) {
					lb[j] = label[z];
					j++;
				}
				optimize(size, lb);
			}
		}
	}
	
	public void importNearestUser(Map<String, Integer> map) throws IOException {
		int MAX_BLOCK_SIZE = 1000;
		
		String[] match;
		match = new String[map.keySet().size()];
		for (String user: map.keySet()) {
			int index = map.get(user);
			match[index] = user;
		}
		HTable table = new HTable(NeighbourTable.NAME);
		List<Put> puts = Lists.newArrayList();
		int count = 0;
		try {
			for (int index: nearest.keySet()) {
				String s = nearest.get(index);
				String userId = match[index];
				byte[] row = Bytes.toBytes(userId);
				String[] chunks = s.split(",");
				StringBuilder sb = new StringBuilder();
				for (int i = 0; i < chunks.length; i++) {
					int code = Integer.parseInt(chunks[i]);
					sb.append(match[code]).append(",");
				}
				StringUtils.deleteLastChar(sb);
				byte[] value = Bytes.toBytes(sb.toString());
				Put put = new Put(row);
				put.add(NeighbourTable.FAM_MAIN, NeighbourTable.COL_NEAREST, value);
				puts.add(put);
				count++;
				if (count == MAX_BLOCK_SIZE) {
					table.put(puts);
					puts = Lists.newArrayList();
					count = 0;
				}
			}
			if (count > 0)
				table.put(puts);
		} finally {
			table.close();
		}
	}
	
	public void test(int n_) {
		Random rand = new Random(System.currentTimeMillis());
		new Data(n_); // create database
		for (int i = 0; i < n_; i++) {
			int d = 30;
			for (short j = 0; j < d; j++) {
				int state = rand.nextInt(3);
				short p;
				if (state == 0)
					p = 0;
				else
					p = (short)rand.nextInt(10);
				Data.add(i, j, p);
			}
		}		
		Data.initial();
		int[] label = new int[n_];
		for (int i = 0; i < n_; i++)
			label[i] = i;
		optimize(n_, label);		
	}
	
	public void display() {
		for (int userid: nearest.keySet()) {
			String s = nearest.get(userid);
			String[] chunks = s.split(",");
			System.out.print(userid + ": \t");
			for (int i = 0; i < chunks.length; i++) {
				int near = Integer.parseInt(chunks[i]);
				double score = Data.distance(userid, near);
				System.out.print("[" + near + ", " + score + "]   ");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) throws IOException {
		long start = System.currentTimeMillis();
		KNN knn = new KNN(38);
		knn.test(1000000);
		knn.display();
		long end = System.currentTimeMillis();
		System.out.println("Total time used: " + (end - start) + " ms");
	}

}
